// https://www.lintcode.com/problem/non-decreasing-array/

public class Solution {
    /**
     * @param nums: an array
     * @return: if it could become non-decreasing by modifying at most 1 element
     */
    public boolean checkPossibility(int[] nums) {
        // Write your code here
        int p = -1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i -1] > nums[i]) {
                p = i; // 可疑位，进一步验证。
                break;
            }
        }
        if (p > 0) {
            int prev;
            if (p == 1) { // 第一元素比第二个大，需要特别处理
                // 后面的元素要递并且比nums[1]大，因为nums[0]可以变小。
                prev = nums[p]; 
            } else {
                // ..., n[p - 1], n[p]，n[p]调整为n[p - 1]，后面如满足条件不能小于n[p - 1]。
                prev = nums[p - 1]; 
            }
            for (int i = p + 1; i < nums.length; ++i) {
                if (nums[i] < prev) {
                    return false;
                }
                prev = nums[i];
            }
        }
        return true;
    }
}